package com.leetcode.demo3Solution.JianOffer;

/**
 * @description:
 * @author: cyy
 **/
public class offer04_0603 {
    public static void main(String[] args) {
    int[][] a={{-1},{-1}};
    System.out.println("shitutuya:"+findNumberIn2DArrayNew(a,4));

    }


    //暴力法
    public static  boolean findNumberIn2DArray(int [][] matrix, int target) {
        boolean result=false;
        //获取二维数组的长度，子数组的长度
        int n=matrix.length;
        if (n>0){
            int m=matrix[0].length;
            int[] arr=matrix[0];
            //如果二维数组长度为1
            if (n==1){
                for (int i=0;i<m;i++){
                    if (arr[i]==target){
                        result = true;
                    }
                }
            }else {
                //遍历一次可能会存在
                for (int j=0;j<n;j++){
                    for (int q=0;q<m;q++){
                        if (target==matrix[j][q]){
                            result = true;
                        };
                    }

                }
            }
        }
        return  result;
    }

    //二叉搜索树从小到上
    public static  boolean findNumberIn2DArrayNew(int [][] matrix, int target) {
        int i=matrix.length-1,j=0;
        while (i>0 && j<matrix[0].length){
            if (target>matrix[i][j]) {
                i--;
            }
            else if (target <matrix[i][j]) {
                j++;
            }else {
                return  true;
            }
        }
        return  false;

        /*
        int i = matrix.length - 1, j = 0;
        while(i >= 0 && j < matrix[0].length)
        {
            if(matrix[i][j] > target) i--;
            else if(matrix[i][j] < target) j++;
            else return true;
        }
        return false;
        *
        *
        *
        * */
    }

    //二叉搜索树从上到下
    public static  boolean findNumberIn2DArrayNew1(int [][] matrix, int target) {
        int i=0,j=matrix[0].length-1;
        while (j>0 && i< matrix.length){
            if (target<matrix[i][j]) {
                j--;
            }
            else if (target >matrix[i][j]) {
                i++;
            }else {
                return  true;
            }
        }
        return  false;
    }
}
